/**
 * Created by JiaJia on 2019/5/23 0023.
 *机器人的运动范围
 * 用DFS的思想求解
 * 与矩阵中的路径的区别是，已标记的走过的格子，不需要重置
 */
public class Code67 {
    public int movingCount(int threshold, int rows, int cols)
    {
        int[][] flag=new int[rows][cols];
        return helper(threshold,rows,cols,0,0,flag);
    }
    private int helper(int threshold, int rows, int cols,int i,int j,int[][] flag){
        if (i<0||i>=rows||j<0||j>=cols||sum(i)+sum(j)>threshold||flag[i][j]==1){
            return 0;
        }
        flag[i][j]=1;
        return helper(threshold,rows,cols,i-1,j,flag)
                +helper(threshold,rows,cols,i+1,j,flag)
                +helper(threshold,rows,cols,i,j-1,flag)
                +helper(threshold,rows,cols,i,j+1,flag)
                +1;

    }
    private int sum(int k){
        int sum=0;
        while (k>0){
            sum+=k%10;
            k=k/10;
        }
        return sum;
    }
}